
/* Double linked lists implementations */
#include <stdio.h>
#include <stdlib.h>

#include "dlinkedlists.h"
#include "fibheap.h"
#include "mex.h"
/*
 function insertAfter(List list, Node node, Node newNode)
     newNode.prev := node
     newNode.next := node.next
     if node.next == null
         list.lastNode := newNode
     else
         node.next.prev := newNode
     node.next := newNode
 */
void dll_insertAfter(DoublyLinkedList *list, DoublyLinkedNode *node, DoublyLinkedNode *newNode) {
    newNode->prev = node;
    newNode->next = node->next;
    if (node->next == NULL)
        list->lastNode = newNode;
    else
        node->next->prev = newNode;
    node->next = newNode;
    
    list->n++;
}

/*
 function insertBefore(List list, Node node, Node newNode)
     newNode.prev := node.prev
     newNode.next := node
     if node.prev == null
         list.firstNode := newNode
     else
         node.prev.next := newNode
     node.prev    := newNode
 */
void dll_insertBefore(DoublyLinkedList *list, DoublyLinkedNode *node, DoublyLinkedNode *newNode) {
    newNode->prev = node->prev;
    newNode->next = node;
    if (node->prev == NULL)
        list->firstNode = newNode;
    else
        node->prev->next = newNode;
    node->prev = newNode;
    
    list->n++;
}

/*
 function insertBeginning(List list, Node newNode)
     if list.firstNode == null
         list.firstNode := newNode
         list.lastNode  := newNode
         newNode.prev := null
         newNode.next := null
     else
         insertBefore(list, list.firstNode, newNode)
 */
void dll_insertBeginning(DoublyLinkedList *list, DoublyLinkedNode *newNode) {
    if (list->firstNode == NULL) {
        list->firstNode = newNode;
        list->lastNode = newNode;
        newNode->prev = NULL;
        newNode->next = NULL;
        
        list->n++;
    }
    else
        dll_insertBefore(list, list->firstNode, newNode);
}

/*
 function insertEnd(List list, Node newNode)
     if list.lastNode == null
         insertBeginning(list, newNode)
     else
         insertAfter(list, list.lastNode, newNode)
 */
void dll_insertEnd(DoublyLinkedList *list, DoublyLinkedNode *newNode) {
    if (list->lastNode == NULL)
        dll_insertBeginning(list, newNode);
    else
        dll_insertAfter(list, list->lastNode, newNode);
}

/*
 function remove(List list, Node node)
   if node.prev == null
       list.firstNode := node.next
   else
       node.prev.next := node.next
   if node.next == null
       list.lastNode := node.prev
   else
       node.next.prev := node.prev
   destroy node
 */
DoublyLinkedNode *dll_remove(DoublyLinkedList *list, DoublyLinkedNode *node) {
    if (node->prev == NULL)
        list->firstNode = node->next;
    else
        node->prev->next = node->next;
    
    if (node->next == NULL)
        list->lastNode = node->prev;
    else
        node->next->prev = node->prev;
    
    node->prev = NULL;
    node->next = NULL;
    
    list->n--;
    
    return(node);
        
}

DoublyLinkedNode *dll_new_node(void *data) {
    DoublyLinkedNode *node;
    node=malloc(sizeof(DoublyLinkedNode));
    node->data=data;
    node->prev=NULL;
    node->next=NULL;
    
    return(node);
}

int dll_free_node(DoublyLinkedNode *node) {
    if (node != NULL)
        free(node);
    else
        return 1;
    
    return 0;
}

DoublyLinkedList *dll_new_list() {
    DoublyLinkedList* l;
    l=malloc(sizeof(DoublyLinkedList));
    l->firstNode = NULL;
    l->lastNode = NULL;
    l->n=0;
    
    return(l);
}

int dll_free_list(DoublyLinkedList *list) {
    
    DoublyLinkedNode *tmp, *tmp2;
    int i;
    
    if (list != NULL) {
        tmp = list->firstNode;
        for (i=0; i<list->n; i++) {
            tmp2 = tmp->next;
            dll_free_node(tmp);
            tmp=tmp2;
        }
        free(list);
    }
    else
        return 1;
    
    return 0;
}

void dll_debug(DoublyLinkedList *list) {
    DoublyLinkedNode *x, *y;
    fibNode *fnode;
    
    mexPrintf("-- List Size: %d\n",list->n);
    
    for (x=list->firstNode; x!=NULL;) {
        y = x->next;
        
        fnode = x->data;
        
        mexPrintf("%f ", ((double)(fnode->key)));
        
        x=y;
    }
    
    mexPrintf("\n--\n");
    
    
    /*if (list->lastNode != NULL && list->firstNode != NULL) {
        tmp = list->firstNode;
        for (i=1; i<list->n; i++) {
            fnode = tmp->data;
            mexPrintf("%f-", ((double)(fnode->key)));
            tmp=tmp->next;
        }
        if (list->n > 1) {
            fnode = list->lastNode->data;
            mexPrintf("%f\n", ((double)(fnode->key)));
        }
    }*/
}

